package list

import "sort"

// Problem Definition: https://leetcode.cn/problems/longest-increasing-subsequence/

func LengthofLISI(nums []int) (ret int) {
	n := len(nums)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[j]+1, dp[i])
			}
		}
		ret = max(ret, dp[i])
	}

	return ret
}

func LengthofLISI1(nums []int) int {
	var piles []int
	for i := range nums {
		idx := sort.SearchInts(piles, nums[i])

		if idx == len(piles) {
			piles = append(piles, nums[i])
		} else {
			piles[idx] = nums[i]
		}
	}

	return len(piles)
}
